package SearchAlgorithm;

import java.util.Arrays;

// 斐波那契查找算法(黄金分割法 0.618)
public class FibonacciSearch {

    // 斐波那契数列的长度为20
    static final int MAXSIZE = 20;

    // 生成斐波那契数列
    public void generateFibonacci(int[] f) {
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < MAXSIZE; i++) {
            f[i] = f[i-1] + f[i-2];
        }
    }

    // 斐波那契查找
    public int fibonacciSearch(int[] arr, int target, int len){
        int low = 0; // 表示每次查找的最低位
        int high = len - 1;// 每次查找范围的最高位
        int mid = 0; // 每次查找范围的一个黄金比例位
        int k = 0; // 对应斐波那契数列中的索引
        int fibonacci[] = new int[MAXSIZE]; // 斐波那契数列
        int i;

        // 将斐波那契数列初始化
        generateFibonacci(fibonacci);

        //根据数组的长度为F[k] - 1 来决定需要多少个斐波那契数值
        while(fibonacci[k] - 1 < len){
            ++k;
        }

        // 因为f[k]的值有可能大于数组的长度，我们需要构造一个长度为f[k]新的数组
        int[] temp = Arrays.copyOf(arr, fibonacci[k]);
        // 将长度不足的部分 填充为数组的最后一位数
        for (i = len; i < fibonacci[k]; i++) {
            temp[i] = arr[high];
        }

        while (low <= high){
            mid = low + fibonacci[k-1] - 1;

            // 如果目标值比mid小
            if(target < temp[mid]){
                high = mid - 1;
                k = k - 1; // 这里单独解释，请看代码下方的问题1解答
            }else if(target > temp[mid]){
                low = mid + 1;
                k -= 2; // 请看代码下方的问题2解答
            }else{
                return Math.min(mid,high);
            }
        }

        return -1;
    }

    // main
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 42, 1000, 1234};
        FibonacciSearch fibonacciSearch = new FibonacciSearch();
        int r = fibonacciSearch.fibonacciSearch(arr,1234,arr.length);
        System.out.println(r);
    }
}
